/**
 * 
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
 * 在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 */


// 暴力循环
let nums = [0, 1, 2, 3, 4, 5, 6, 7, 9];

let missingNumber1 = function(nums) {
    for (let i = 0; i < nums.length; i++) {
        if (i !== nums[i]) {
            return i;
        }
    }
    return nums.length;

};


/**
 * 
 * 二分法
 * 时间复杂度 O(logN)： 二分法为对数级别复杂度。
 * 空间复杂度 O(1)： 几个变量使用常数大小的额外空间。
 */
let missingNumber2 = function(nums) {
    let [i, j, m] = [0, nums.length - 1, 0];
    while (i <= j) {
        m = Math.floor((i + j) / 2);
        if (nums[m] === m) {
            i = m + 1;
        } else {
            j = m - 1;
        }
    }
    return i;

};


// 测试算法
let resp = missingNumber2(nums);
console.log(resp);